<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>K-means算法 | Hexo</title>
  <meta name="keywords" content=" AI , 机器学习 ">
  <meta name="description" content="K-means算法 | Hexo">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构">
<meta property="og:url" content="http://yoursite.com/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="第二章 线性表线性表：表内数据类型相同，有限序列 本章将以总结的形式展现： 2.1 顺序表与链式表的区别     顺序表 链式表     存取 随机存取 顺序存取   结构 顺序存储（连续） 随机存储（不连续）   空间分配 静态存储（可以动态分配） 动态存储   操作 查找 O(1) ,插入和删除O（n） 查找 O(n) ,插入和删除O（1）   缺点 插入删除不便，长度不可以改变 查找速度慢，">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171844-136893.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/203103-111988.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171839-101678.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/200119-510473.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/05/113954-515448.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/203146-263519.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153239-688589.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153248-836462.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153259-101399.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202103/11/113055-306258.jpeg">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/151817-474283.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/103950-168345.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/02/105245-140913.png">
<meta property="og:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/19/153313-134836.png">
<meta property="article:published_time" content="2021-03-11T16:00:00.000Z">
<meta property="article:modified_time" content="2021-03-11T07:19:09.038Z">
<meta property="article:author" content="MOLU">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/moluggg/image/raw/master/img/202102/23/171951-630686.png">


<link rel="icon" href="/img/avatar.jpg">

<link href="/css/style.css?v=1.1.0" rel="stylesheet">

<link href="/css/hl_theme/github.css?v=1.1.0" rel="stylesheet">

<link href="//cdn.jsdelivr.net/npm/animate.css@4.1.0/animate.min.css" rel="stylesheet">

<script src="//cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="/js/titleTip.js?v=1.1.0" ></script>

<script src="//cdn.jsdelivr.net/npm/highlightjs@9.16.2/highlight.pack.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.jsdelivr.net/npm/nprogress@0.2.0/nprogress.min.js"></script>



<script src="//cdn.jsdelivr.net/npm/jquery.cookie@1.4.1/jquery.cookie.min.js" ></script>

<script src="/js/iconfont.js?v=1.1.0" ></script>

<meta name="generator" content="Hexo 5.0.0"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="">
  <input class="theme_blog_path" value="">
  <input id="theme_shortcut" value="true" />
</div>


<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/" class="avatar_target">
    <img class="avatar" src="/img/avatar.jpg" />
</a>
<div class="author">
    <span>MOLU</span>
</div>

<div class="icon">
    
        
        <a title="rss" href="/atom.xml" target="_blank">
            
                <i class="iconfont icon-rss"></i>
            
        </a>
        
    
        
        <a title="github" href="https://github.com/molu-ggg" target="_blank">
            
                <i class="iconfont icon-github"></i>
            
        </a>
        
    
        
    
        
    
        
        <a title="email" href="mailto:2572876783@qq.com" target="_blank">
            
                <i class="iconfont icon-email"></i>
            
        </a>
        
    
</div>




<ul>
    <li><div class="all active" data-rel="All">All<small>(35)</small></div></li>
    
        
            
            <li><div data-rel="AI论文">AI论文<small>(5)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="专业知识">专业知识<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="数学">数学<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="机器学习">机器学习<small>(12)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="经典算法">经典算法<small>(10)</small></div>
                
            </li>
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/about">About</a><a style="width: 50%"  class="friends">Friends</a></div>
</div>
<input type="hidden" id="yelog_site_posts_number" value="35">

<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        Links
        <i class="iconfont icon-left"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <div class="right-top">
        <div id="default-panel">
            <i class="iconfont icon-search" data-title="搜索 快捷键 i"></i>
            <div class="right-title">All</div>
            <i class="iconfont icon-file-tree" data-title="切换到大纲视图 快捷键 w"></i>
        </div>
        <div id="search-panel">
            <i class="iconfont icon-left" data-title="返回"></i>
            <input id="local-search-input" />
            <label class="border-line" for="input"></label>
            <i class="iconfont icon-case-sensitive" data-title="大小写敏感"></i>
            <i class="iconfont icon-tag" data-title="标签"></i>
        </div>
        <div id="outline-panel" style="display: none">
            <div class="right-title">大纲</div>
            <i class="iconfont icon-list" data-title="切换到文章列表"></i>
        </div>
    </div>

    <div class="tags-list">
    <input id="tag-search" />
    <div class="tag-wrapper">
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>50</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>AI</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>数据结构，最短路径，图</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>机器学习</a>
            </li>
        
            <li class="article-tag-list-item">
                <i class="iconfont icon-tag"></i><a>相似度计算</a>
            </li>
        
    </div>

</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="All 经典算法 "
           href="/2020/07/20/b_leetcode/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="leetcode &amp; 蓝桥">leetcode &amp; 蓝桥</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a id="top" class="All AI论文 "
           href="/2020/07/10/d_GAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAT">GAT</span>
            <span class="post-date" title="2020-07-10 08:50:20">2020/07/10</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%BB%84%E6%88%90%E5%8E%9F%E7%90%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="计算机组成原理">计算机组成原理</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 专业知识 "
           href="/2021/03/12/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数据结构">数据结构</span>
            <span class="post-date" title="2021-03-12 00:00:00">2021/03/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/12/05/b_%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E4%B8%8E%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划记忆化">动态规划记忆化</span>
            <span class="post-date" title="2020-12-05 00:00:00">2020/12/05</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/25/d_300-paperDAT/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="DAT for recommender">DAT for recommender</span>
            <span class="post-date" title="2020-07-25 08:50:20">2020/07/25</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="算法总结">算法总结</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All 数学 "
           href="/2020/07/20/a_%E6%95%B0%E5%AD%A6/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="数学">数学</span>
            <span class="post-date" title="2020-07-20 00:00:00">2020/07/20</span>
        </a>
        
        <a  class="All "
           href="/2020/07/05/%E5%AF%B9%E9%9A%90%E7%A7%98%E7%9A%84%E8%A7%92%E8%90%BD%E7%94%B5%E8%A7%86%E5%89%A7%E7%9A%84%E6%84%9F%E6%82%9F%E4%BB%A5%E5%8F%8A%E8%AE%A4%E8%AF%86/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="对隐秘的角落电视剧的感悟以及认识">对隐秘的角落电视剧的感悟以及认识</span>
            <span class="post-date" title="2020-07-05 00:00:00">2020/07/05</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/07/04/a_%E6%A8%A1%E6%9D%BF%E5%BA%93/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="模板库">模板库</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/07/04/a_%E7%99%BE%E5%BA%A6%E6%8A%80%E6%9C%AF%E8%AE%A4%E8%AF%81/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="百度技术认证">百度技术认证</span>
            <span class="post-date" title="2020-07-04 08:50:20">2020/07/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/07/01/d_GCN%E8%AE%BA%E6%96%87%E8%A7%A3%E8%AF%BB/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GCN">GCN</span>
            <span class="post-date" title="2020-07-01 08:50:20">2020/07/01</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/06/04/d_word2vec_node2vec/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="Word2vec &amp; Node2vec">Word2vec &amp; Node2vec</span>
            <span class="post-date" title="2020-06-04 08:50:20">2020/06/04</span>
        </a>
        
        <a  class="All AI论文 "
           href="/2020/05/05/d_GAN/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="GAN">GAN</span>
            <span class="post-date" title="2020-05-05 08:50:20">2020/05/05</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/05/04/d_Deepwalk/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="DEEPWALK">DEEPWALK</span>
            <span class="post-date" title="2020-05-04 08:50:20">2020/05/04</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/15/b_%E8%B4%AA%E5%BF%83/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="贪心与动态规划">贪心与动态规划</span>
            <span class="post-date" title="2020-02-15 00:00:00">2020/02/15</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/02/12/a_2020/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="机器学习零散知识记录">机器学习零散知识记录</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/12/b_%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="动态规划——背包问题">动态规划——背包问题</span>
            <span class="post-date" title="2020-02-12 00:00:00">2020/02/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/02/03/b_%E8%93%9D%E6%A1%A5%E6%9D%AF%E7%BB%83%E4%B9%A0%E9%A2%98/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="蓝桥杯">蓝桥杯</span>
            <span class="post-date" title="2020-02-03 00:00:00">2020/02/03</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2020/01/20/c_%E5%86%B3%E7%AD%96%E6%A0%91/"
           data-tag="50"
           data-author="" >
            <span class="post-title" title="决策树总结">决策树总结</span>
            <span class="post-date" title="2020-01-20 00:00:00">2020/01/20</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2020/01/12/b_%E5%85%A8%E6%8E%92%E5%88%97/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="全排列">全排列</span>
            <span class="post-date" title="2020-01-12 00:00:00">2020/01/12</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/12/02/b_%E6%9C%89%E7%A9%B7%E8%87%AA%E5%8A%A8%E6%9C%BA/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="有穷自动机">有穷自动机</span>
            <span class="post-date" title="2019-12-02 00:00:00">2019/12/02</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/11/20/b_%E9%94%99%E6%8E%92%E5%85%AC%E5%BC%8F/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="错排公式">错排公式</span>
            <span class="post-date" title="2019-11-20 00:00:00">2019/11/20</span>
        </a>
        
        <a  class="All "
           href="/2019/10/29/a_%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7/"
           data-tag="数据结构，最短路径，图"
           data-author="" >
            <span class="post-title" title="最短路径之弗洛伊德算法">最短路径之弗洛伊德算法</span>
            <span class="post-date" title="2019-10-29 00:00:00">2019/10/29</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/04/c_BPR/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="贝叶斯">贝叶斯</span>
            <span class="post-date" title="2019-08-04 08:50:20">2019/08/04</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/08/02/c_matrix/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="矩阵分解与正则化">矩阵分解与正则化</span>
            <span class="post-date" title="2019-08-02 08:25:59">2019/08/02</span>
        </a>
        
        <a  class="All "
           href="/2019/07/28/c_coordination1/"
           data-tag="AI,机器学习,相似度计算"
           data-author="" >
            <span class="post-title" title="协同过滤-上">协同过滤-上</span>
            <span class="post-date" title="2019-07-28 08:25:59">2019/07/28</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/26/c_cnn/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="cnn">cnn</span>
            <span class="post-date" title="2019-07-26 18:54:51">2019/07/26</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_coordination2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="协同过滤—下">协同过滤—下</span>
            <span class="post-date" title="2019-07-22 18:54:26">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/22/c_kmeans/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="K-means算法">K-means算法</span>
            <span class="post-date" title="2019-07-22 18:53:07">2019/07/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/07/21/c_nerve2/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络-下">神经网络-下</span>
            <span class="post-date" title="2019-07-21 11:37:18">2019/07/21</span>
        </a>
        
        <a  class="All "
           href="/2019/07/20/c_nerve1/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="神经网络—上">神经网络—上</span>
            <span class="post-date" title="2019-07-20 17:29:10">2019/07/20</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/22/c_gradient/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归与梯度下降算法">线性回归与梯度下降算法</span>
            <span class="post-date" title="2019-06-22 08:26:36">2019/06/22</span>
        </a>
        
        <a  class="All 机器学习 "
           href="/2019/06/19/c_flyback/"
           data-tag="AI,机器学习"
           data-author="" >
            <span class="post-title" title="线性回归">线性回归</span>
            <span class="post-date" title="2019-06-19 00:00:00">2019/06/19</span>
        </a>
        
        <a  class="All 经典算法 "
           href="/2019/05/20/b_%E8%A7%86%E9%A2%91%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95/"
           data-tag=""
           data-author="" >
            <span class="post-title" title="简单入门算法">简单入门算法</span>
            <span class="post-date" title="2019-05-20 00:00:00">2019/05/20</span>
        </a>
        
        <div id="no-item-tips">

        </div>
    </nav>
    <div id="outline-list">
    </div>
</div>
    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div id="post">
    <div class="pjax">
        <article id="post-c_kmeans" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">K-means算法</h1>
    
    <div class="article-meta">
        
        
        
        <span class="book">
            <i class="iconfont icon-category"></i>
            
            
            <a  data-rel="机器学习">机器学习</a>
            
        </span>
        
        
        <span class="tag">
            <i class="iconfont icon-tag"></i>
            
            <a class="color3">AI</a>
            
            <a class="color5">机器学习</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
            Created At : <time class="date" title='Updated At: 2020-08-09 14:28:07'>2019-07-22 18:53</time>
        
    </div>
    <div class="article-meta">
        
        
        <span id="busuanzi_container_page_pv">
            Views 👀 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#K-means%E7%AE%97%E6%B3%95"><span class="toc-text">K-means算法</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E8%81%9A%E7%B1%BB"><span class="toc-text">聚类</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%AD%A5%E9%AA%A4%EF%BC%9A"><span class="toc-text">算法步骤：</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E5%A4%A7%E7%BA%B2"><span class="toc-text">算法大纲</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-%E8%87%AA%E5%AE%9A%E4%B9%89%E5%88%9B%E5%BB%BAk%E4%B8%AA%E7%82%B9%E4%BD%9C%E4%B8%BA%E8%B5%B7%E5%A7%8B%E6%94%AF%E7%82%B9-%E9%9A%8F%E6%9C%BA%E9%80%89%E6%8B%A9"><span class="toc-text">1.自定义创建k个点作为起始支点(随机选择)</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2-%E5%BD%93%E4%BB%BB%E6%84%8F%E4%B8%80%E4%B8%AA%E7%B0%87%E7%9A%84%E5%88%86%E9%85%8D%E7%BB%93%E6%9E%9C%E5%8F%91%E7%94%9F%E6%94%B9%E5%8F%98%E7%9A%84%E6%97%B6%E5%80%99"><span class="toc-text">2.当任意一个簇的分配结果发生改变的时候</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3-%E8%AE%A1%E7%AE%97%E7%82%B9%E5%BF%83%E4%B9%8B%E9%97%B4%E8%B7%9D%E7%A6%BB%E5%B9%B6%E5%88%86%E9%85%8D%E7%82%B9%E5%88%B0%E6%9C%80%E8%BF%91%E7%9A%84%E5%BF%83%E7%9A%84%E9%82%A3%E4%B8%80%E7%B0%87"><span class="toc-text">3.计算点心之间距离并分配点到最近的心的那一簇</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4-%E5%AF%B9%E6%AF%8F%E4%B8%80%E7%B0%87%EF%BC%8C%E8%AE%A1%E7%AE%97%E7%B0%87%E4%B8%AD%E6%89%80%E6%9C%89%E7%82%B9%E7%9A%84%E5%9D%87%E5%80%BC%E5%B9%B6%E5%B0%86%E5%85%B6%E5%9D%87%E5%80%BC%E4%BD%9C%E4%B8%BA%E8%B4%A8%E5%BF%83"><span class="toc-text">4.对每一簇，计算簇中所有点的均值并将其均值作为质心</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%85%B7%E4%BD%93%E6%AD%A5%E9%AA%A4"><span class="toc-text">具体步骤</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#Step1-K%E5%80%BC%E7%9A%84%E9%80%89%E6%8B%A9"><span class="toc-text">Step1.K值的选择</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Step2-%E8%B7%9D%E7%A6%BB%E5%BA%A6%E9%87%8F"><span class="toc-text">Step2.距离度量</span></a><ol class="toc-child"><li class="toc-item toc-level-5"><a class="toc-link" href="#2-1-%E6%AC%A7%E5%BC%8F%E8%B7%9D%E7%A6%BB"><span class="toc-text">2.1.欧式距离</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-2-%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB"><span class="toc-text">2.2.曼哈顿距离</span></a></li><li class="toc-item toc-level-5"><a class="toc-link" href="#2-3-%E4%BD%99%E5%BC%A6%E7%9B%B8%E4%BC%BC%E5%BA%A6"><span class="toc-text">2.3.余弦相似度</span></a></li></ol></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Step3-%E6%96%B0%E8%B4%A8%E5%BF%83%E7%9A%84%E8%AE%A1%E7%AE%97"><span class="toc-text">Step3.新质心的计算</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#Step4-%E6%98%AF%E5%90%A6%E5%81%9C%E6%AD%A2K-means"><span class="toc-text">Step4.是否停止K-means</span></a></li></ol></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Python%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-text">Python代码实现</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#iris"><span class="toc-text">iris</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%AC%A7%E5%BC%8F%E8%B7%9D%E7%A6%BB"><span class="toc-text">欧式距离</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%9A%8F%E6%9C%BA%E8%B4%A8%E5%BF%83"><span class="toc-text">随机质心</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#k%E5%9D%87%E5%80%BC%E8%81%9A%E7%B1%BB"><span class="toc-text">k均值聚类</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%B0%8F%E7%BB%93"><span class="toc-text">小结</span></a></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h1 id="K-means算法"><a href="#K-means算法" class="headerlink" title="K-means算法"></a>K-means算法</h1><p><strong><em>图片显示不出来可刷新</em></strong></p>
<a id="more"></a>
<h1 id="聚类"><a href="#聚类" class="headerlink" title="聚类"></a>聚类</h1><p>​        对于”<strong>监督学习</strong>“(supervised learning)，其训练样本<strong>是带有标记信息</strong>的，并且监督学习的<strong>目的是</strong>：从给定的训练数据集中学习出一个函数（模型参数），当新的数据到来时，可以根据这个函数预测结果。</p>
<p>​       而在“<strong>无监督学习</strong>”(unsupervised learning)中，不少情况下无法预先知道样本的标签，也就是说没有训练样本对应的类别，因而只能从原先没有样本标签的样本集开始学习分类器设计,<strong>目标是</strong>通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。对于无监督学习，应用最广的便是”<strong>聚类</strong>“(clustering)。<br>​        “<strong>聚类算法</strong>“试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”(cluster)，通过这样的划分，每个簇可能对应于一些潜在的概念或类别。</p>
<p>​         K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。</p>
<p>​         k个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。</p>
<h1 id="算法步骤："><a href="#算法步骤：" class="headerlink" title="算法步骤："></a>算法步骤：</h1><h3 id="算法大纲"><a href="#算法大纲" class="headerlink" title="算法大纲"></a>算法大纲</h3><h4 id="1-自定义创建k个点作为起始支点-随机选择"><a href="#1-自定义创建k个点作为起始支点-随机选择" class="headerlink" title="1.自定义创建k个点作为起始支点(随机选择)"></a>1.自定义创建k个点作为起始支点(随机选择)</h4><h4 id="2-当任意一个簇的分配结果发生改变的时候"><a href="#2-当任意一个簇的分配结果发生改变的时候" class="headerlink" title="2.当任意一个簇的分配结果发生改变的时候"></a>2.当任意一个簇的分配结果发生改变的时候</h4><h4 id="3-计算点心之间距离并分配点到最近的心的那一簇"><a href="#3-计算点心之间距离并分配点到最近的心的那一簇" class="headerlink" title="3.计算点心之间距离并分配点到最近的心的那一簇"></a>3.计算点心之间距离并分配点到最近的心的那一簇</h4><ul>
<li>对每个质心 <ul>
<li>计算质心与数据点之间的距离</li>
</ul>
</li>
<li>将数据分配到距离其最近的簇</li>
</ul>
<h4 id="4-对每一簇，计算簇中所有点的均值并将其均值作为质心"><a href="#4-对每一簇，计算簇中所有点的均值并将其均值作为质心" class="headerlink" title="4.对每一簇，计算簇中所有点的均值并将其均值作为质心"></a>4.对每一簇，计算簇中所有点的均值并将其均值作为质心</h4><h3 id="具体步骤"><a href="#具体步骤" class="headerlink" title="具体步骤"></a>具体步骤</h3><p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183716.png" alt="没图片请重新加载"></p>
<h4 id="Step1-K值的选择"><a href="#Step1-K值的选择" class="headerlink" title="Step1.K值的选择"></a>Step1.K值的选择</h4><p>k 的选择一般是按照实际需求进行决定，或在实现算法时直接给定 k 值。（k也就是上图点的个数）</p>
<blockquote>
<p>说明：<br><strong>A</strong>.质心数量由用户给出，记为k，k-means最终得到的簇数量也是k<br><strong>B</strong>.后来每次更新的质心的个数都和初始k值相等<br><strong>C</strong>.k-means最后聚类的簇个数和用户指定的质心个数相等，一个质心对应一个簇，每个样本只聚类到一个簇里面<br><strong>D</strong>.初始簇为空</p>
</blockquote>
<h4 id="Step2-距离度量"><a href="#Step2-距离度量" class="headerlink" title="Step2.距离度量"></a>Step2.距离度量</h4><p>​        将对象点分到距离聚类中心最近的那个簇中需要最近邻的度量策略，在欧式空间中采用的是欧式距离，在处理文档中采用的是余弦相似度函数，有时候也采用曼哈顿距离作为度量，不同的情况实用的度量公式是不同的。</p>
<p>​         刚开始时分别计算数据到k个点的距离，并选择最近的簇心归类。</p>
<p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183738.png" alt=""></p>
<h5 id="2-1-欧式距离"><a href="#2-1-欧式距离" class="headerlink" title="2.1.欧式距离"></a><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183758.png" alt="">2.1.欧式距离</h5><p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183818.png" alt=""></p>
<h5 id="2-2-曼哈顿距离"><a href="#2-2-曼哈顿距离" class="headerlink" title="2.2.曼哈顿距离"></a>2.2.曼哈顿距离</h5><p><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183838.png" alt=""></p>
<h5 id="2-3-余弦相似度"><a href="#2-3-余弦相似度" class="headerlink" title="2.3.余弦相似度"></a>2.3.余弦相似度</h5><p>​        A与B表示向量(x1,y1)，(x2,y2)<br>​        分子为A与B的点乘，分母为二者各自的L2相乘，即将所有维度值的平方相加后开方。<br><img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183903.png" alt=""></p>
<blockquote>
<p>说明：<br><strong>A</strong>.经过step2，得到k个新的簇，每个样本都被分到k个簇中的某一个簇<br><strong>B</strong>.得到k个新的簇后，当前的质心就会失效，需要计算每个新簇的自己的新质心</p>
</blockquote>
<h4 id="Step3-新质心的计算"><a href="#Step3-新质心的计算" class="headerlink" title="Step3.新质心的计算"></a>Step3.新质心的计算</h4><p>​        对于分类后的产生的k个簇，分别计算到簇内其他点距离均值最小的点作为质心（对于拥有坐标的簇可以计算每个簇坐标的均值作为质心）</p>
<blockquote>
<p>说明：<br><strong>A</strong>.比如一个新簇有3个样本：[[1,4], [2,5], [3,6]]，得到此簇的新质心=[(1+2+3)/3, (4+5+6)/3]<br><strong>B</strong>.经过step3，会得到k个新的质心，作为step2中使用的质心</p>
</blockquote>
<h4 id="Step4-是否停止K-means"><a href="#Step4-是否停止K-means" class="headerlink" title="Step4.是否停止K-means"></a>Step4.是否停止K-means</h4><p>​        质心不再改变，或给定loop最大次数loopLimit</p>
<blockquote>
<p>说明：<br><strong>A</strong>当每个簇的质心，不再改变时就可以停止k-menas<br><strong>B</strong>.当loop次数超过looLimit时，停止k-means<br><strong>C</strong>.只需要满足两者的其中一个条件，就可以停止k-means<br><strong>C</strong>.如果Step4没有结束k-means，就再执行step2-step3-step4<br><strong>D</strong>.如果Step4结束了k-means，则就打印(或绘制)簇以及质心</p>
</blockquote>
<h1 id="Python代码实现"><a href="#Python代码实现" class="headerlink" title="Python代码实现"></a>Python代码实现</h1><h2 id="iris"><a href="#iris" class="headerlink" title="iris"></a>iris</h2><p>我们用非常著名的iris数据集。</p>
<pre><code class="lang-python">from sklearn import datasets
import matplotlib.pyplot as plt
iris = datasets.load_iris()
X, y = iris.data, iris.target
data = X[:,[1,3]] # 为了便于可视化，只取两个维度
plt.scatter(data[:,0],data[:,1]);
</code></pre>
<h2 id="欧式距离"><a href="#欧式距离" class="headerlink" title="欧式距离"></a>欧式距离</h2><p>计算欧式距离，我们需要为每个点找到离其最近的质心，需要用这个辅助函数。</p>
<pre><code class="lang-python">def distance(p1,p2):
    &quot;&quot;&quot;
    Return Eclud distance between two points.
    p1 = np.array([0,0]), p2 = np.array([1,1]) =&gt; 1.414
    &quot;&quot;&quot;
    tmp = np.sum((p1-p2)**2)
    return np.sqrt(tmp)

distance(np.array([0,0]),np.array([1,1]))
1.4142135623730951
</code></pre>
<h2 id="随机质心"><a href="#随机质心" class="headerlink" title="随机质心"></a>随机质心</h2><p>在给定数据范围内随机产生k个簇心，作为初始的簇。随机数都在给定数据的范围之内<code>dmin + (dmax - dmin) * np.random.rand(k)</code>实现。</p>
<pre><code class="lang-python">def rand_center(data,k):
    &quot;&quot;&quot;Generate k center within the range of data set.&quot;&quot;&quot;
    n = data.shape[1] # features
    centroids = np.zeros((k,n)) # init with (0,0)....
    for i in range(n):
        dmin, dmax = np.min(data[:,i]), np.max(data[:,i])
        #这一行代码原理及作用不清楚：i=0,就是所有x坐标比较大小，然后i=1时y坐标比较大小，i=3时z....
        centroids[:,i] = dmin + (dmax - dmin) * np.random.rand(k)#质点的位置选取范围，i=0时选x坐标,i=1时选y坐标
    return centroids

centroids = rand_center(data,2)
centroids
array([[ 2.15198267,  2.42476808],
       [ 2.77985426,  0.57839675]])
</code></pre>
<h2 id="k均值聚类"><a href="#k均值聚类" class="headerlink" title="k均值聚类"></a>k均值聚类</h2><p>这个基本的算法只需要明白两点。</p>
<ul>
<li>给定一组质心，则簇更新，所有的点被分配到离其最近的质心中。</li>
<li>给定k簇，则质心更新，所有的质心用其簇的均值替换</li>
</ul>
<p>当簇不在有更新的时候，迭代停止。当然kmeans有个缺点，就是可能陷入局部最小值，有改进的方法，比如二分k均值，当然也可以多计算几次，去效果好的结果。</p>
<pre><code class="lang-python">def kmeans(data,k=2):
    def _distance(p1,p2):#计算距离
        &quot;&quot;&quot;
        Return Eclud distance between two points.
        p1 = np.array([0,0]), p2 = np.array([1,1]) =&gt; 1.414
        &quot;&quot;&quot;
        tmp = np.sum((p1-p2)**2)
        return np.sqrt(tmp)
    def _rand_center(data,k):#随机在范围内选取质心
        &quot;&quot;&quot;Generate k center within the range of data set.&quot;&quot;&quot;
        n = data.shape[1] # features
        centroids = np.zeros((k,n)) # init with (0,0)....
        for i in range(n):
            dmin, dmax = np.min(data[:,i]), np.max(data[:,i])
            centroids[:,i] = dmin + (dmax - dmin) * np.random.rand(k)
        return centroids

    def _converged(centroids1, centroids2):

        # if centroids not changed, we say &#39;converged&#39;
         set1 = set([tuple(c) for c in centroids1])
         set2 = set([tuple(c) for c in centroids2])
         return (set1 == set2)


    n = data.shape[0] # 样本数据集个数
    centroids = _rand_center(data,k)#质点的取值范围
    label = np.zeros(n,dtype=np.int) #？？？？ track the nearest centroid
    assement = np.zeros(n) # for the assement of our model
    converged = False

    while not converged:
        old_centroids = np.copy(centroids)
        for i in range(n):
            # determine the nearest centroid and track it with label
            min_dist, min_index = np.inf, -1
            for j in range(k):
                dist = _distance(data[i],centroids[j])
                if dist &lt; min_dist:
                    min_dist, min_index = dist, j
                    label[i] = j
            assement[i] = _distance(data[i],centroids[label[i]])**2

        # update centroid
        for m in range(k):
            centroids[m] = np.mean(data[label==m],axis=0)
        converged = _converged(old_centroids,centroids)    
    return centroids, label, np.sum(assement)
</code></pre>
<p>由于算法可能局部收敛的问题，随机多运行几次，取最优值</p>
<pre><code class="lang-python">best_assement = np.inf
best_centroids = None
best_label = None

for i in range(10):
    centroids, label, assement = kmeans(data,2)
    if assement &lt; best_assement:
        best_assement = assement
        best_centroids = centroids
        best_label = label

data0 = data[best_label==0]
data1 = data[best_label==1]
</code></pre>
<p>如下图，我们把数据分为两簇，绿色的点是每个簇的质心，从图示效果看，聚类效果还不错。</p>
<pre><code class="lang-python">fig, (ax1,ax2) = plt.subplots(1,2,figsize=(12,5))
ax1.scatter(data[:,0],data[:,1],c=&#39;c&#39;,s=30,marker=&#39;o&#39;)
ax2.scatter(data0[:,0],data0[:,1],c=&#39;r&#39;)
ax2.scatter(data1[:,0],data1[:,1],c=&#39;c&#39;)
ax2.scatter(centroids[:,0],centroids[:,1],c=&#39;b&#39;,s=120,marker=&#39;o&#39;)
plt.show()
</code></pre>
<p> <img src="https://moluggg.oss-cn-qingdao.aliyuncs.com/img/20190824183921.png" alt=""></p>
<p>链接：<a target="_blank" rel="noopener" href="https://www.jianshu.com/p/5314834f9f8e">https://www.jianshu.com/p/5314834f9f8e</a></p>
<h1 id="小结"><a href="#小结" class="headerlink" title="小结"></a>小结</h1><p>1.聚类与分类的区别</p>
<p>2.监督学习与无监督学习</p>
<p>3.算法的局限性： <a target="_blank" rel="noopener" href="https://www.cnblogs.com/zhizhan/p/4083654.html">https://www.cnblogs.com/zhizhan/p/4083654.html</a></p>
<ul>
<li>[ ] 4.距离公式的使用方法</li>
</ul>
<p>本文参：<a target="_blank" rel="noopener" href="https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html">https://www.cnblogs.com/jerrylead/archive/2011/04/06/2006910.html</a></p>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2572876783@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">💰</a>
</p>






    
        <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
    "HTML-CSS": {
        preferredFont: "TeX",
        availableFonts: ["STIX","TeX"],
        linebreaks: { automatic:true },
        EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
        inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
        processEscapes: true,
        ignoreClass: "tex2jax_ignore|dno",
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
        equationNumbers: { autoNumber: "AMS" },
        noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
        Macros: { href: "{}" }
    },
    messageStyle: "none"
    });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
        src="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<input type="hidden" id="MathJax-js"
        value="//cdn.jsdelivr.net/npm/mathjax@2.7.8/unpacked/MathJax.js?config=TeX-MML-AM_CHTML">
</input>
    




    </div>
    <div class="copyright">
        <p class="footer-entry">
    ©2016-2020 MOLU
</p>
<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<a class="" id="rocket" ></a>

    </div>
</div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>Help us with donation</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">alipay</label></span><span><label><input type="radio" name="pay" value="weixin">weixin</label></span>
    </div>
</div>


</body>
<script src="/js/jquery.pjax.js?v=1.1.0" ></script>

<script src="/js/script.js?v=1.1.0" ></script>
<script>
    var img_resize = 'default';
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $("#post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 542px;
    }
    .nav.fullscreen {
        margin-left: -542px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 492px;
        }
        .nav.fullscreen {
            margin-left: -492px;
        }
        .nav-left {
            width: 100px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 492px;
            margin-left: -492px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>







</html>
